package week_02;

/**
 * 560. 和为K的子数组
 * 给定一个整数数组和一个整数k，你需要找到该数组中和为k的连续的子数组的个数。
 * <p>
 * 示例 1 :
 * <p>
 * 输入:nums = [1,1,1], k = 2
 * 输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。
 * 说明 :
 * <p>
 * 数组的长度为 [1, 20,000]。
 * 数组中元素的范围是 [-1000, 1000] ，且整数k的范围是[-1e7, 1e7]。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/subarray-sum-equals-k
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class SubarrayKSum_560 {
    // 这种做法是错误，会有遗漏，需要使用前缀和 sum[i]-k 在前缀和 0～ i-1 存在几次 ans 就++；
    public int subarraySum(int[] nums, int k) {
        int ans = 0;
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            int add = 0;
            for (int j = i; j < n; j++) {
                add = add + nums[j];
                if (add == k) {
                    ans++;
                }
            }
        }
        return ans;
    }

    // 这种做法是错误，会有遗漏，需要使用前缀和 sum[i]-k 在前缀和 0～ i-1 存在几次 ans 就++；
    public int subarraySum1(int[] nums, int k) {
        int n = nums.length;
        int ans = 0;
        for (int i = 0; i < n; i++) {
            int add = 0;
            int j = i ;
            // 因为 数组并没有单调性，用单指针，是难以控制范围边界的
            while (!(add > k) && j < n) {
                add = add + nums[j];
                System.out.println("add::"+add+"::nums[j]::"+nums[j]);
                if (add==k) {
                    ans+=1;
                }
                j++;
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        SubarrayKSum_560 test = new SubarrayKSum_560();
        int[] arr = new int[]{1, -1, 0};
        System.out.println(test.subarraySum(arr, 0));
    }
}
